package solutions;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-28
 * Time: 11:02
 */

//https://leetcode.cn/problems/maximum-subarray/description/
//线段树，分治算法（类似归并排序）
class Solution1 {

    public static class Status {
        public int lSum;//左遍开始的最大值
        public int rSum;//右边开始的最大值
        public int mSum;//最大值
        public int iSum;//整个区间的和

        //构造方法
        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length - 1).mSum;
    }

    public Status getInfo(int[] a, int l, int r) {
        if (l == r) {//分治为一个数
            return new Status(a[l], a[l], a[l], a[l]);//全部初始化为该数
        }
        int m = (l + r) >> 1;//相当于/2
        //分
        Status lSub = getInfo(a, l, m);
        Status rSub = getInfo(a, m + 1, r);//不能重复
        return pushUp(lSub, rSub);//合
    }

    public Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;//总和为左总＋右总
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);//左和与左和+右左选出最大的
        int rSum = Math.max(r.rSum, l.rSum + r.iSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }
}


